package com.leetcode;

import com.leetcode.common.TreeNode;

import java.util.LinkedList;
import java.util.List;

/**
 * 235. 二叉搜索树的最近公共祖先
 * 1. 先分别找从root到p或p在树中的路径
 * 2. 通过比对路径, 找到第一个公共的节点, 该节点就是最近公共祖先
 *
 * @author fy
 * @date 2022/4/25 20:54
 */
public class Solution235_3 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> set1 = findNode(root, p);
        List<TreeNode> set2 = findNode(root, q);
        for (int i = set1.size() - 1; i >= 0; i--) {
            TreeNode item1 = set1.get(i);
            for (int j = set2.size() - 1; j >= 0; j--) {
                TreeNode item2 = set2.get(j);
                // 这里有一个前提是所有节点的值都是唯一的, 就是值不会重复
                if (item1.val == item2.val) {
                    return item1;
                }
            }
        }
        return null;
    }
    // 找路径的方法有待完善
    private List<TreeNode> findNode(TreeNode root, TreeNode p) {
        List<TreeNode> setTree = new LinkedList<>();
        if (root == null) {
            return setTree;
        }
        setTree.add(root);
        if (root.val == p.val) {
            return setTree;
        }
        if (root.val > p.val) {
            setTree.addAll(findNode(root.left, p));
        } else {
            setTree.addAll(findNode(root.right, p));
        }
        return setTree;
    }

}
